Problem 989 Add to Array-Form of Integer
将一个数组组成的数和给定的数相加,返回list
主要思路:
这个题目属于大数相加的类型,要是采用数组转化成数字的形式必然会出现溢出的问题,所以还是得采用逐位变化的方式求解.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public List<Integer> addToArrayForm(int[] A, int K) {
LinkedList<Integer> ret=new LinkedList<>();
int i=A.length-1;
while(K!=0 || i>=0)
{
int p=i>=0?A[i]:0;
ret.add(0,(K+p)%10);
K=(K+p)/10;
i--;
}
return ret;
}
}
代码说明:
以[2,1,5]+806为例,进入循环后首先将i>=0?的结果赋值给p,这里是为了防止数组的最高位相加后依然要进位的情况,因为如果不判断是否大于0的话会因为K!=0而使得i=-1发生越界.
此时p=5,ret链表在头部插入(K+p)%10==1,K=81,i=1;p=1,ret头部插入(K+p)%10==2,K=8,i=0;p=2,ret头部插入(K+p)%10==0,K=1,i=-1.p=-1取0,ret插入1,K=0,i=-2结束.
Problem 1002 Find Common Characters
寻找字符串数组中共有的字符,允许出现共有重复字符.
主要思路:
这种类型的题目都可以使用开辟新的数组,通过数据统计方式解决.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public List<String> commonChars(String[] A) {
int n = A.length;
int[][] cc = new int[n][26];
for (int i = 0; i < n; i++) {
for (char c : A[i].toCharArray()) {
cc[i][c - 'a']++;
}
}
List<String> result = new ArrayList<>();
for (int i = 0; i < 26; i++) {
int minCount = 100;
for (int j = 0; j < n; j++) {
minCount = Math.min(minCount, cc[j][i]);
}
for (int j = 0; j < minCount; j++) {
result.add(String.valueOf((char) (i + 'a')));
}
}
return result;
}
}
代码说明:
首先遍历数组,统计每个字符串中各个字符的数量多少.之后按照字符数量对字符串进行检查,比如要是所有的字符串中都出现了两次m,则m的minCount就是2,如果出现某个字符未出现则其必定为0,所以可以统计出结果.
Problem 1005 Maximize Sum Of Array After K Negations
将数组中的K个数字取反后求数组最大和
主要思路:
每次取排序数组后的最小值,将其取反,这样必然会求出最大值,但是如果每次都排序的话性能较差,可以采用堆排序的方式和取前K小的思路.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public int largestSumAfterKNegations(int[] A, int K) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for(int x: A)
pq.add(x);
while( K--> 0)
pq.add(-pq.poll());
int sum = 0;
for(int i = 0; i < A.length; i++){
sum += pq.poll();
}
return sum;
}
}
Problem 1009 Complement of Base 10 Integer
先将十进制转成二进制,之后将1转成0,从0转成1,得出结果.
主要思路:
传统来说就是按照题目意思转二进制再逐位取反,但是可以使用位操作的方式进行.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public int bitwiseComplement(int N) {
if (N == 0)
return 1;
int bit_count = 0, x = N;
while ( x != 0) {
x /= 2;
bit_count++;
}
return ((1 << bit_count) - 1) ^ N;
}
}
代码说明:
主要是最后一句,<<是左移运算符,移动过程中符号位不变,高位溢出并舍弃,低位补0.数字a进行左移by运算结果等于a*2b,以10为例,其bit_count=4,1左移4位变成16,16-1=15,之后15和10按位异或,1111^1010=0101求得翻转后的二进制.这里主要是利用了异或的性质,1^1=0,0^0=0,所以先统计需要求解的数字有多少位,将其减1后可以得出全1的二进制,和原数取异或即可完成翻转.
Problem 1013 Partition Array Into Three Parts With Equal Sum
判断一个数组的是否存在三个子数组的和相同.
主要思路:
这个题目看起来很复杂,需要判断多个连续子数组的和的相等情况,但其实这个题目挺简单的.因为题目限定了三个子数组,那么如果和不能被3整除则必然不满足条件.第二个就是将数组顺序累加,每次达到sum/3则重置累加器,遍历结束后判断此时累加器是不是等于0.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public boolean canThreePartsEqualSum(int[] A) {
int sum = IntStream.of(A).sum();
if (sum % 3 != 0)
return false;
int target = IntStream.of(A).sum() / 3;
int currentSum = 0;
for (int i = 0; i < A.length; i++) {
currentSum += A[i];
if (currentSum == target){
currentSum = 0;
}
}
return currentSum == 0;
}
}
Problem 1029 Two City Scheduling
公司总共需要安排2N的人进行面试,其中一半的人要去A,另一半的人要去B,给定每个人去城市A和城市B的费用,要求求出最小的总费用安排.
主要思路:
首先计算出每个候选人去A和B城市的费用差值,比如第一位候选人去A花费90,去B花费100,则差值为-10,这样我们就知道他去A城费用更低,这样据此进行排序,并取前一半的人去A城,剩下的去B城.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public int twoCitySchedCost(int[][] costs) {
Arrays.sort(costs, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return (a[0] - a[1]) - (b[0] - b[1]);
}
});
int sum = 0;
for (int i = 0; i < costs.length; ++i) {
if (i < costs.length / 2) {
sum += costs[i][0];
} else {
sum += costs[i][1];
}
}
return sum;
}
}
Problem 1033 Moving Stones Until Consecutive
给定三块石子的位置,移动石子直到三个石子顺序相邻,求出使得三个石子顺序相邻的最小移动步数和最大移动步数.
主要思路:
最小步数最多不超过2步:
- 0步:三个石子已经顺序排列
- 1步:三个石子中两个已经顺序排列或者两个石子隔一个位置,将剩下的的这个插到中间即可.
- 2步:把非中间位的两个石子移动到中间位的两边.
最大步数为最大值-最小值-2: - 以7 10 14为例,7->9花费2步,14->11花费3步,故为max-min-2
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public int[] numMovesStones(int a, int b, int c) {
int max = Math.max(a, Math.max(b, c));
int min = Math.min(a, Math.min(b, c));
int mid = a + b + c - max - min;
int min_moves = Math.min(1, mid-min-1) +Math.min(1, max-mid-1);
if (mid-min == 2 || max-mid == 2) {
min_moves = 1;
}
int max_moves = max - min - 2;
return new int[]{min_moves, max_moves};
}
}
Problem 1042 Flower Planting With No Adjacent
类似于地图着色问题,相连接的两朵花园的花的种类不能相同.
主要思路:
首先构建图,知道每个花园的入度和出度,然后遍历花园,给当前花园放置与其连接的花园不相同的花.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32class Solution {
public int[] gardenNoAdj(int N, int[][] paths) {
List<Integer>[] graph = new List[N+1];
for(int[] path : paths){
if(graph[path[0]] == null)
graph[path[0]] = new LinkedList<Integer>();
graph[path[0]].add(path[1]);
if(graph[path[1]] == null)
graph[path[1]] = new LinkedList<Integer>();
graph[path[1]].add(path[0]);
}
int[] cols = new int[N];
Set<Integer> set = new HashSet();
for(int i = 1 ; i <= N;i++){
if(graph[i] == null || cols[i-1]!=0)
continue;
set.clear();
for(int nNode:graph[i]){
if(cols[nNode-1]!=0)
set.add(cols[nNode-1]);
}
for(int index = 1;index <= 4 && cols[i-1] == 0 ;index++)
if(!set.contains(index)){
cols[i-1] = index;
}
}
for(int i = 0 ; i<N;i++)
if(cols[i] == 0)
cols[i] =1;
return cols;
}
}
Problem 1175 Prime Arrangements
给定正整数n,返回从1到n之间质数在质数位置的全部数组的个数.
主要思路:
这题看似很复杂,题目中提到了排列问题,但其实这个问题是一个很简单的排列组合问题.首先列出题目范围内的质数,求出n之内有多少质数,这些质数如果是X个,则占据X位,共有X!种排法,剩下的非质数自然有(n-X)!种排法,所以总共有两者乘积个数组满足题目条件.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34class Solution {
public int numPrimeArrangements(int n) {
int mod = 1000000007;
int primeNums = countPrime(n);
int nonPrimeNums = n - primeNums;
long result = 1;
for (int i=2; i<=primeNums; i++) {
result = (result*i)%mod;
}
for (int j=2; j<=nonPrimeNums; j++) {
result = (result*j)%mod;
}
return (int)result;
}
public int countPrime(int n) {
if (n <= 1) {
return 0;
}
int count = 0;
for (int i = 2; i <= n; i++) {
boolean flag = true;
for (int j = 2; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
flag = false;
break;
}
}
if (flag) {
count++;
}
}
return count;
}
}